import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class MyQueue {
    //理由LinkedList实现了队列
    static class ListNode{
        public ListNode next;
        public ListNode prev;
        public int val;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode first;
    public ListNode last;
    public int usedSize = 0;

    //1.尾插
    public void offer(int val) {
        ListNode node=new ListNode(val);
        if(isEmpty()){
            first=last=node;
        }else{
            last.next=node;
            node.prev=last;
            last=last.next;
        }
        usedSize++;
    }

    //2.头删,考虑只有一个节点的情况
    public int poll() {
        if(isEmpty()){
            return -1;
        }else{
            int val= first.val;
            first=first.next;
            //如果只有一个节点
            if(first!=null){
                first.prev=null;
            }
            usedSize--;
            return val;

        }

    }

    public int peek() {
        if(isEmpty()){
            return -1;
        }
        int val= first.val;
        return val;
    }
    public boolean isEmpty() {
        return usedSize==0;
    }
    class MyCircularQueue {
        //.这道题相遇不一定是在0下标相遇
        //也可以在其他下标相遇
        public int Front;
        public int Rear;
        public int[] elem;


        public MyCircularQueue(int k) {
            //要k+1,因为只用了k个
            elem=new int[k+1];
        }
        //插入元素
        public boolean enQueue(int value) {
            if(isFull()){
                return false;
            }
            elem[Rear]=value;
            Rear=(Rear+1)%elem.length;
            return true;
        }
        //删除元素
        public boolean deQueue() {
            if(isEmpty()){
                return false;
            }
            int val=elem[Front];
            Front=(Front+1)%elem.length;
            return true;

        }
        //获取队头元素
        public int Front() {
            if(isEmpty()){
                return -1;
            }
            return elem[Front];
        }

        public int Rear() {
            if(isEmpty()){
                return -1;
            }
            int index = (Rear == 0) ? elem.length-1 : Rear-1;
            return elem[index];

        }

        public boolean isEmpty() {
            return Rear==Front;

        }

        public boolean isFull() {
            return (Rear+1)%elem.length==Front;

        }
    }
    class MyStack {
        //这道题的qu1与qu2只会出现三种情况
        //qu1与qu2全部为空
        //qu1为空，qu2不为空
        //qu1不为空，qu2为空
        public Queue<Integer> qu1;
        public Queue<Integer> qu2;

        public MyStack() {
            qu1=new LinkedList<>();
            qu2=new LinkedList<>();
        }

        public void push(int x) {
            if(!qu2.isEmpty()){
                qu2.offer(x);
            }else{
                qu1.offer(x);
            }
        }
        //相当于得到栈顶的元素
        public int pop() {
            if(empty()){
                return -1;
            }
            if(!qu1.isEmpty()){
                int size=qu1.size();
                for(int i=0;i<size-1;i++){
                    qu2.offer(qu1.poll());
                }
                return qu1.poll();
            }else{
                int size=qu2.size();
                for(int i=0;i<size-1;i++){
                    qu1.offer(qu2.poll());
                }
                return qu2.poll();
            }
        }
        //相当于栈的peek()
        public int top() {
            if(empty()){
                return -1;
            }
            if(!qu1.isEmpty()){
                int size=qu1.size();
                int j=0;
                for(int i=0;i<size;i++){
                    j=qu1.poll();
                    qu2.offer(j);
                }
                return j;
            }else{
                int size=qu2.size();
                int j=0;
                for(int i=0;i<size;i++){
                    j=qu2.poll();
                    qu1.offer(j);
                }
                return j;
            }
        }

        public boolean empty() {
            return qu1.isEmpty()&&qu2.isEmpty();

        }
    }
    class MyQueue1 {
        Deque<Integer> stack1;
        Deque<Integer> stack2;

        public MyQueue1() {
            stack1=new ArrayDeque<>();//双端队列,既可以作为栈，也可以作为队列，
            stack2=new ArrayDeque<>();
        }

        public void push(int x) {//直接把所有的值都放入stack1中，stack1只负责入，而stack2只管出
            stack1.push(x);
        }

        public int pop() {
            if(empty()){
                return -1;
            }
            if(stack2.isEmpty()){
                int size=stack1.size();
                for(int i=0;i<size;i++){
                    int ret=stack1.pop();//如果没有ret是错的,没有ret，则有些stack1.pop()就会丢失
                    stack2.push(ret);
                }
                return stack2.pop();
            }else{
                return stack2.pop();
            }

        }

        public int peek() {
            if(empty()){
                return -1;
            }
            if(stack2.isEmpty()){
                int size=stack1.size();
                for(int i=0;i<size;i++){
                    int ret=stack1.pop();
                    stack2.push(ret);
                }
                return stack2.peek();
            }else{
                return stack2.peek();
            }
        }

        public boolean empty() {
            return stack1.isEmpty()&&stack2.isEmpty();

        }
    }


}
